#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;

// 快速幂，求a^b mod p
int power(int a, int b, int p)
{
    int ans = 1;
    for (; b; b >>= 1)
    {
        if (b & 1)
            ans = (long long)ans * a % p;
        a = (long long)a * a % p;
    }
    return ans;
}

// 64位整数乘法的O(log b)算法
ll mul(ll a, ll b, ll p)
{
    long long ans = 0;
    for (; b; b >>= 1)
    {
        if (b & 1)
            ans = (ans + a) % p;
        a = a * 2 % p;
    }
    return ans;
}

// 64位整数乘法的long double算法
ull mul(ull a, ull b, ull p)
{
    a %= p, b %= p; // 当a,b一定在0~p之间时，此行不必要
    ull c = (long double)a * b / p;
    ull x = a * b, y = c * p;
    long long ans = (long long)(x % p) - (long long)(y % p);
    if (ans < 0)
        ans += p;
    return ans;
}

int main()
{

    return 0;
}
